from typing import List


class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        ans = 0
        stat = 0
        last = 0
        for num in nums:
            if stat == 0:  # 当前正在找偶数
                if num >= last:
                    last = num
                else:
                    ans += last
                    last = num
                    stat = 1
            else:  # 当前正在找奇数
                if num <= last:
                    last = num
                else:
                    ans -= last
                    last = num
                    stat = 0

        if stat == 0:
            ans += last

        return ans


if __name__ == "__main__":
    print(Solution().maxAlternatingSum([4, 2, 5, 3]))  # 7
    print(Solution().maxAlternatingSum([5, 6, 7, 8]))  # 8
    print(Solution().maxAlternatingSum([6, 2, 1, 2, 4, 5]))  # 10
